package main

func main() {

	a := 1000

	//打印测试用例返回结果
	resp := mySqrt(a)
	println(resp)

}

//二分查找
func mySqrt(a int) int {
	if a == 1 || a == 0 {
		return a
	}
	temp := a / 2 //从2开始，所有比2大的数字，除以2(向下取整)的值的平方，肯定小于等于该数字本身

	//对temp进行二分查找
	for true {
		if judge(temp, a) == "eq" { //找到了，返回！
			return temp
		}
		//标准的二分法了
		start, end := 0, temp
		for true {
			mid := (start + end) / 2
			judge := judge(mid, a)
			if judge == "eq" {
				return mid
			} else if judge == "lt" {
				start = mid + 1
			} else { //其实就是gt的情况
				end = mid - 1
			}
		}
	}
	return 0

}
func mySqrt(x int) int {

}

//判断一个整数的平方，是否符合题设条件（等于或刚好小于target）
func judge(num, target int) string {
	//知识点：|| 和 && 同时出现，会先算&&。也就是说&&优先级更高
	if num*num == target || num*num < target && (num+1)*(num+1) > target { //满足条件，返回eq
		return "eq"
	} else { //如果不满足条件，可以返回两种状态
		if num*num < target {
			return "lt"
		} else {
			return "gt"
		}
	}
}
